Preferential Attachment

Outline

- Basic Simulation and Plot: alpha = 1
- Experiement 1: alpha = 1
- Experiement 2: alpha < 1
- Experiement 3: alpha > 1
- How Networkx Preferential Attachment Differs
- Based on the paper: https://arxiv.org/pdf/cond-mat/0104131.pdf



In [58]:

    
import networkx as netx
import numpy as np
import matplotlib.pyplot as plt

import warnings
import random
import itertools



In [59]:

    
def power_law_graph(G): 
    histo = netx.degree_histogram(G)
    _ = plt.loglog(histo, 'b-', marker='o')
    _ = plt.ylabel("k(x)")
    _ = plt.xlabel("k")
    plt.show()

def plot(T,skew=True):
    plt.axis('off')
    
    pos=netx.spring_layout(T)
    
    if skew:
        D = dict(netx.degree(T))
        sizes = [v * 200 for k,v in D.items()]
        netx.draw_networkx(T, pos=pos, with_labels=True, nodelist=D.keys(), node_size=sizes)
    else:
        netx.draw_networkx(T, pos=pos, with_labels=True)
        
    plt.show()
    
def hist(T,bins=25):
    degree_lookup = dict(netx.degree(T))
    degrees = list(degree_lookup.values())

    _ = plt.title("Degree Distribution")
    _ = plt.hist(degrees,bins=bins)
    plt.show()
    
def generate(nodes):
    n = 0
    while n < nodes:
        n = n + 1
        yield n



In [60]:

    
# number of attachments per round
m = 1

# nodes at time t = 0
a = 1
t0 = m + a

# build graph
G = netx.Graph()

paths = list(generate(t0))
G.add_path(paths)



In [61]:

    
plot(G)



In [62]:

    
## builds a distribution node sequence
def linear_distribute(G,disregard=[]):
    for node in G.nodes(data = False):
        if node in disregard:
            continue
        
        for edge in netx.edges(G,node):
            yield node
            
# randomly gets attachments of the new node
def get_linear_attachments(G,m=1):
    if m < 1:
        return []
    
    nodes = []
    
    i = 0
    while i < m:
        distribution = list(linear_distribute(G,disregard=nodes))
        nodes.append(random.choice(distribution))
        i = i + 1
        
    return nodes

def simulate(G,node,m=1,rounds=100):
    while node <= rounds:
        attachments = get_linear_attachments(G,m=m)
        
        G.add_node(node)
        for attachment in attachments:
            G.add_edge(node,attachment)

        node = node + 1

Simulation



In [63]:

    
T = G.copy()
simulate(T,m+1,m,rounds=15)



In [64]:

    
plot(T,skew=True)

Experiment 1

- Alpha = 1, 
- hypothesis: degree distribution should be exponential,



In [65]:

    
# ramp up...
T1 = G.copy()
simulate(T1,m+1,m,rounds=3000)



In [66]:

    
hist(T1)



In [67]:

    
power_law_graph(T1)

Experiment 2

- Alpha < 1,
- Hypothesis: degree distribution should be a stretched exponential,



In [68]:

    
def draw(G,disregard=[],alpha=1):
    
    nodes = { }
    lookup = dict(G.degree())

    denominator = 0.0
    for k,v in lookup.items():
        if k in disregard:
            continue
        
        nodes[k] = (v ** alpha)
        denominator = denominator + nodes[k]

    #print(np.array(list(nodes.values()))/denominator)
    
    drawing = random.uniform(0,1)
    
    key = None
    bottom = 0.0
    top = 0.0
    
    for k,v in nodes.items():
        key = k
        top = bottom + (v / denominator)
        
        if (drawing >= bottom) & (drawing < top):
            key = k
            break
        
        bottom = top
    
    # print(drawing, " ", bottom, "-", top, ":", key)
    return key

# randomly gets attachments of the new node
def get_attachments(G,alpha=1,m=1):
    if m < 1:
        return []
    
    nodes = []
    
    i = 0
    while i < m:
        node = draw(G,disregard=nodes,alpha=alpha)
        nodes.append(node)
        i = i + 1
    
    # print()
    return nodes

def simulate2(G,node,alpha=1,m=1,rounds=100):
    while node <= rounds:
        attachments = get_attachments(G,alpha,m=m)  
        G.add_node(node)
        
        for attachment in attachments:
            G.add_edge(node,attachment)

        node = node + 1


T2 = G.copy()
simulate2(T2,m+1,.5,m,3000)



In [69]:

    
hist(T2)



In [70]:

    
power_law_graph(T2)

Experiment 3

- Alpha > 1,
- Hypothesis: degree distribution should be gelation-like phenomenon,
    - means m nodes should have a majority of the connections



In [71]:

    
T3 = G.copy()
simulate2(T3,m+1,3.5,m,3000)



In [72]:

    
hist(T3)



In [73]:

    
nodes = sorted(list(dict(T3.degree()).values()),reverse=True)

# print segment of list out ...
nodes[0:5]









    Out[73]:





[2999, 1, 1, 1, 1]



In [74]:

    
power_law_graph(T3)

Networkx

- computes the preferential attachment score,
- Preferential Attachment Score: Indicates the likelihood of a new link forming between two nodes (u,v). 
                                 Multiplication of the friends of u and v (1).

References:

https://books.google.com/books?id=F2cPpfcpor8C&pg=PA294&lpg=PA294&dq=what+is+preferential+attachment+score&source=bl&ots=G1yfDyOsO_&sig=JcuDjT9wQyH4a0mHcBzNgxIoalU&hl=en&sa=X&ved=0ahUKEwjAjqb6p6fXAhVPVWMKHU5cBTEQ6AEIazAL#v=onepage&q=what%20is%20preferential%20attachment%20score&f=false



In [75]:

    
T4 = netx.generators.random_graphs.barabasi_albert_graph(8,1)
plot(T4)



In [76]:

    
scores = netx.preferential_attachment(G=T4)
for u,v,score in scores:
    print('(%d, %d) -> score = %d' % (u, v, score))









    



(0, 2) -> score = 2
(0, 3) -> score = 4
(0, 4) -> score = 2
(0, 6) -> score = 2
(0, 7) -> score = 2
(1, 4) -> score = 5
(1, 5) -> score = 5
(2, 3) -> score = 2
(2, 4) -> score = 1
(2, 5) -> score = 1
(2, 6) -> score = 1
(2, 7) -> score = 1
(3, 5) -> score = 2
(3, 6) -> score = 2
(3, 7) -> score = 2
(4, 5) -> score = 1
(4, 6) -> score = 1
(4, 7) -> score = 1
(5, 6) -> score = 1
(5, 7) -> score = 1
(6, 7) -> score = 1



In [77]:

    
len(list(T4.neighbors(1))) * len(list(T4.neighbors(7)))









    Out[77]:





5